/**
 * CS 2110 - Fall 2011 - Homework #11
 * Edited by: Brandon Whitehead
 *
 * list.c: Complete the functions!
 **/
 
/*
Kyle Kelly
CS2110-B2
HW11
*/

#include <stdlib.h>
#include <stdio.h>
#include "list.h"

/* The node struct.  Has a prev pointer, next pointer, and data. */
/* DO NOT DEFINE ANYTHING OTHER THAN WHAT'S GIVEN OR YOU WILL GET A ZERO*/
/* Design consideration only this file should know about nodes */
/* Only this file should be manipulating nodes */
typedef struct lnode
{
  struct lnode* prev; /* Pointer to previous node */
  struct lnode* next; /* Pointer to next node */
  void* data; /* User data */
} node;


/* Do not create any global variables here. Your linked list library should obviously work for multiple linked lists */
// This function is declared as static since you should only be calling this inside this file.
static node* create_node(void* data);

/** create_list
  *
  * Creates a list by allocating memory for it on the heap.
  * Be sure to initialize size to zero and head to NULL.
  *
  * @return an empty linked list
  */
list* create_list(void)
{
	list *llist = (list*) malloc(sizeof(list));
	llist -> head = NULL;
	llist -> size = 0;
	return llist;
}

/** create_node
  *
  * Helper function that creates a node by allocating memory for it on the heap.
  * Be sure to set its pointers to NULL.
  *
  * @param data a void pointer to data the user wants to store in the list
  * @return a node
  */
static node* create_node(void* data)
{
	node *newNode = (node*)malloc(sizeof(node));
	newNode->next = NULL;
	newNode->prev = NULL;
	newNode->data = data;
	return newNode;
}

/** push_front
  *
  * Adds the data to the front of the linked list
  *
  * @param llist a pointer to the list.
  * @param data pointer to data the user wants to store in the list.
  */
void push_front(list* llist, void* data)
{
	node *newHead = create_node(data);
	if (is_empty(llist))
	{
		llist ->head = newHead;
		llist ->head->next = newHead;
		llist ->head->prev = newHead;
	}
	else
	{
		//temp = head;
		node *oldHead = llist ->head;
		//head = newNode
		llist ->head = newHead;
		//newnode.next = oldhead
		llist ->head->next = oldHead;
		//newNode.prev = oldhead.prev
		llist ->head->prev = oldHead->prev;
		//newNode.prev.next = newNode
		llist ->head->prev->next = llist->head;
		//oldHead.prev = newHead
		llist ->head->next->prev = llist->head;
	}
	llist->size++;
	//free(oldHead);
}

/** push_back
  *
  * Adds the data to the back/end of the linked list
  *
  * @param llist a pointer to the list.
  * @param data pointer to data the user wants to store in the list.
  */
void push_back(list* llist, void* data)
{
	node *newTail = create_node(data);
	if(is_empty(llist))
	{
		llist->head = newTail;
		llist->head->next = llist->head;
		llist->head->prev = llist->head;
	}else
	{
		node *oldTail = llist->head->prev;
		newTail->prev = oldTail;
		newTail->next = llist->head;
		oldTail->next = newTail;
		llist->head->prev = newTail;
	}
		llist->size++;
}

/** remove_front
  *
  * Removes the node at the front of the linked list
  *
  * @warning Note the data the node is pointing to is also freed. If you have any pointers to this node's data it will be freed!
  *
  * @param llist a pointer to the list.
  * @param free_func pointer to a function that is responsible for freeing the node's data.
  * @return -1 if the remove failed (which is only there are no elements) 0 if the remove succeeded.
  */
int remove_front(list* llist, list_op free_func)
{
	/// @note remember to also free the node itself
	/// @note free_func is a function that is responsible for freeing the node's data only.
	if(is_empty(llist))
		return -1;
	else if(llist->size == 1){
		(*free_func)(llist->head->data);
		free(llist->head);
		llist->head = NULL;
		llist->size--;
		return 0;
	}
	else{
		node* temp = llist->head;
		llist->head = llist->head->next;
		temp->prev->next = llist->head;
		llist->head->prev = temp->prev;
		(*free_func)(temp->data);
		free(temp);
		llist->size--;
		return 0;
	}
}

/** remove_index
  *
  * Removes the indexth node of the linked list
  *
  * @warning Note the data the node is pointing to is also freed. If you have any pointers to this node's data it will be freed!
  *
  * @param llist a pointer to the list.
  * @param index index of the node to remove.
  * @param free_func pointer to a function that is responsible for freeing the node's data.
  * @return -1 if the remove failed 0 if the remove succeeded.
  */
int remove_index(list* llist, int index, list_op free_func)
{
	/// @note Remember to also free the node itself
	/// @note free_func is a function that is responsible for freeing the node's data only.
	if(is_empty(llist)||index>=llist->size)
		return -1;
	if(index == 0)
		remove_front(llist, free_func);
	else{
		node *temp = llist->head;
		for(int i = 0; i<index; i++)
			temp = temp->next;
		temp->next->prev = temp->prev;
		temp->prev->next = temp->next;
		(*free_func)(temp->data);
		free(temp);
		llist->size--;
	}
	return 0;
}

/** remove_back
  *
  * Removes the node at the back of the linked list
  *
  * @warning Note the data the node is pointing to is also freed. If you have any pointers to this node's data it will be freed!
  *
  * @param llist a pointer to the list.
  * @param free_func pointer to a function that is responsible for freeing the node's data.
  * @return -1 if the remove failed 0 if the remove succeeded.
  */
int remove_back(list* llist, list_op free_func)
{
	/// @note Remember to also free the node itself
	/// @note free_func is a function that is responsible for frm/mail/?ui=2&shva=1#inboxeeing the node's data only.
	if(is_empty(llist))
		return -1;
	else if(llist->size == 1){
		(*free_func)(llist->head->data);
		free(llist->head);
		llist->head = NULL;
		llist->size--;
		return 0;
	}
	else{
		node * tempBack  = llist->head->prev;
		llist->head->prev = tempBack->prev;
		tempBack->prev->next = llist->head;
		(*free_func)(tempBack->data);
		free(tempBack);
		llist->size--;
		return 0;
	}
}

/** remove_data
  *
  * Removes ALL nodes whose data is EQUAL to the data you passed in or rather when the comparison function returns true (!0)
  * @warning Note the data the node is pointing to is also freed. If you have any pointers to this node's data it will be freed!
  *
  * @param llist a pointer to the list
  * @param data data to compare to.
  * @param compare_func a pointer to a function that when it returns true it will remove the element from the list and do nothing otherwise @see equal_op.
  * @param free_func a pointer to a function that is responsible for freeing the node's data
  * @return the number of nodes that were removed.
  */
int remove_data(list* llist, const void* data, equal_op compare_func, list_op free_func)
{
	/// @note remember to also free all nodes you remove.
	/// @note free_func is a function that is responsible for freeing the node's data only.
	if(is_empty(llist))
		return 0;
	unsigned int rm, curIdx = 0;
	unsigned int len = llist->size;
	node *temp = llist->head;
	for(unsigned int i = 0; i<len; i++){
		node *curr = temp;
		temp = temp->next;
		if((*compare_func)(data, curr->data)){
			remove_index(llist, curIdx, free_func);
			rm++;
		}
		else
			curIdx++;
	}
	return rm;
}

/** remove_if
  *
  * Removes all nodes whose data when passed into the predicate function returns true
  *
  * @param llist a pointer to the list
  * @param pred_func a pointer to a function that when it returns true it will remove the element from the list and do nothing otherwise @see list_pred.
  * @param free_func a pointer to a function that is responsible for freeing the node's data
  * @return the number of nodes that were removed.
  */
int remove_if(list* llist, list_pred pred_func, list_op free_func)
{
	// @note remember to also free all nodes you remove.
	// @note be sure to call pred_func on the NODES DATA to check if the node needs to be removed.
	// @note free_func is a function that is responsible for freeing the node's data only.
	if(is_empty(llist))
		return 0;
	unsigned int rm = 0;
	unsigned int len = llist->size;
	unsigned int curIdx = 0;
	node *temp = llist->head;
	for(int i = 0; i<len; i++){
		node *curr = temp;
		temp = temp->next;
		if((*pred_func)(curr->data)){
			remove_index(llist, curIdx,free_func);
			rm++;
		}
		else
			curIdx++;
	}
	return rm;
}

/** front
  *
  * Gets the data at the front of the linked list
  * If the list is empty return NULL.
  *
  * @param llist a pointer to the list
  * @return The data at the first node in the linked list or NULL.
  */
void* front(list* llist)
{
	if(is_empty(llist))
		return NULL;
	return llist->head->data;
}

/** get_index
  *
  * Gets the data at the indexth node of the linked list
  * If the list is empty or if the index is invalid return NULL.
  *
  * @param llist a pointer to the list
  * @return The data at the indexth node in the linked list or NULL.
  */
void* get_index(list* llist, int index)
{
	if(llist->size <= index || is_empty(llist))
		return NULL;
	node *temp = llist->head;
	for(int i = 0; i<index;i++)
	{
		temp = temp->next;
	}
	return temp->data;
}

/** back
  *
  * Gets the data at the "end" of the linked list
  * If the list is empty return NULL.
  *
  * @param llist a pointer to the list
  * @return The data at the last node in the linked list or NULL.
  */
void* back(list* llist)
{
	if(is_empty(llist))
		return NULL;
	return llist->head->prev->data;
}

/** is_empty
  *
  * Checks to see if the list is empty.
  *
  * @param llist a pointer to the list
  * @return 1 if the list is indeed empty 0 otherwise.
  */
int is_empty(list* llist)
{
	///@note an empty list by the way we want you to implement it has a size of zero and head points to NULL.
	return ((llist->size==0)&&(llist->head == NULL));
}

/** size
  *
  * Gets the size of the linked list
  *
  * @param llist a pointer to the list
  * @return The size of the linked list
  */
int size(list* llist)
{
	///@note simply return the size of the linked list.  Its that easy!
	return llist->size;
}

/** find_occurence
  *
  * Tests if the search data passed in is in the linked list.
  *
  * @param llist a pointer to a linked list.
  * @param search data to search for the occurence.
  * @param compare_func a pointer to a function that returns true if two data items are equal @see equal_op.
  * @return 1 if the data is indeed in the linked list 0 otherwise.
  */
int find_occurrence(list* llist, const void* search, equal_op compare_func)
{
	if(is_empty(llist))
		return 0;
	node *temp = llist->head;
	for(int i = 0; i<llist->size;i++){
		if((*compare_func)(temp->data, search))
			return 1;
		temp = temp->next;
	}
	return 0;
}

/** empty_list
  *
  * Empties the list after this is called the list should be empty.
  *
  * @param llist a pointer to a linked list.
  * @param free_func function used to free the node's data.
  *
  */
void empty_list(list* llist, list_op free_func)
{
	/// @note Free all of the nodes not the linked list itself.
	/// @note do not free llist.
	if(is_empty(llist));
	else{
		while(is_empty(llist) ==0)
			remove_front(llist, free_func);
	}
}

/** traverse
  *
  * Traverses the linked list calling a function on each node's data.
  *
  * @param llist a pointer to a linked list.
  * @param do_func a function that does something to each node's data.
  */
void traverse(list* llist, list_op do_func)
{
	if(is_empty(llist)==0)
	{
		node *temp = llist->head;
		for(int i = 0; i<llist->size;i++)
		{
			(*do_func)(temp->data);
			temp = temp->next;
		}
	}
}
